/**
 * // Definition for a Node.
 * 
 * */
function TestNode(val, left, right, next) {
    this.val = val === undefined ? null : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
    this.next = next === undefined ? null : next;
}


/**
 * @param {TestNode} root
 * @return {TestNode}
 */
let connect = function (root) {

    if (!root) return root
    innerConn(root.left, root.right)

    // 分别针对三种情况进行连接，因为是完美二叉树，左节点存在的话，右节点一定存在
    function innerConn(left, right) {

        // 如果left.next 已经指定，则跳过
        if (!left || left.next) return
        left.next = right
        // 连接左节点的左右子节点
        innerConn(left.left, left.right)

        // 连接左节点的右子节点和 右节点的子节点
        innerConn(left.right, right.left)

        // 链接右节点的 左右子节点
        innerConn(right.left, right.right)
    }
    return root
};
let input = new TestNode(1, new TestNode(2, new TestNode(4, new TestNode(8), new TestNode(9)), new TestNode(5, new TestNode(10), new TestNode(11))), new TestNode(3, new TestNode(6, new TestNode(12), new TestNode(13)), new TestNode(7, new TestNode(14), new TestNode(15))))

connect(input)

let left = input

do {

    let tempNode = left
    left = tempNode.left
    while (tempNode) {
        console.log(tempNode.val)
        tempNode = tempNode.next
    }
} while (left)